#include "doublelist.h"

/*******************************************************************************
*函数名：
*函数功能：创建空的双向循环链表
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
pnode creat_doublelist(void)
{
	pnode p = (pnode)malloc(sizeof(NODE));
	if(p == NULL)
	{
		perror("malloc");
		return NULL;
	}
	
	p->next = p;
	p->prev = p;
	
	return p;
}

/*******************************************************************************
*函数名：
*函数功能：插入一个节点
*函数参数：	pnode ppre,插入位置的前一个节点
					pnode pnew,要插入的节点
*函数返回值：
*函数说明：通过后插法插入节点
*******************************************************************************/
void insert_node(pnode ppre,pnode pnew)
{
	pnew->next = ppre->next;
	ppre->next->prev = pnew;
	pnew->prev = ppre;
	ppre->next = pnew;
}


/*******************************************************************************
*函数名：
*函数功能：插入一个节点2
*函数参数：	pnode pnext,插入位置的后一个节点
					pnode pnew,要插入的节点
*函数返回值：
*函数说明：通过前插法插入节点
*******************************************************************************/
void insert_node2(pnode pnext,pnode pnew)
{
	pnew->prev = pnext->prev;
	pnext->prev->next = pnew;
	pnew->next = pnext;
	pnext->prev = pnew;
}

/*******************************************************************************
*函数名：
*函数功能：打印链表
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void print_doublelist(pnode head)
{
	pnode p;
	printf("--------------------------------------------\n");
	printf("head");
	for(p = head->next;p != head;p = p->next)
	{
		printf("<->%d",p->data);
	}
	printf("<->head\n");
	printf("--------------------------------------------\n");	
}


/*******************************************************************************
*函数名：
*函数功能：删除一个节点
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void delete_node(pnode pdel)
{
	/*判断链表是否为空*/
	if (isempty_doublelist(pdel))
	{
		printf("链表为空，无法删除\n");
		return;
	}
	
	/*删除节点*/
	pdel->prev->next = pdel->next;
	pdel->next->prev = pdel->prev;
	free(pdel);
}


/*******************************************************************************
*函数名：
*函数功能：删除指定数据对应的节点
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void delete(pnode head,int data)
{
	pnode p = head->next;
	while(p->data != data)
	{
		p = p->next;
		if (p == head)
		{
			printf("该数据对应节点不存在，无法删除。\n");
			return;
		}
	}
	
	delete_node(p);	
}


/*******************************************************************************
*函数名：
*函数功能：判断双向链表是否为空
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
bool isempty_doublelist(pnode head)
{
	if (head->next == head)
		return true;
	else
		return false;
}

/*******************************************************************************
*函数名：
*函数功能：链表翻转
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void reverse_doublelist(pnode head)
{
	pnode p,q;
	p = head->next;//初始记录一下head的后一节点
	
	/*剪切head并让其自循环*/
	cut_node(head);
	head->next = head;
	head->prev = head;
	
	/*不断剪切节点并插入到头节点后*/
	while(p != p->next)
	{
		q = p;
		p = p->next;
		cut_node(q);
		insert_node(head,q);		
	}
	
	insert_node(head,p);
}

/*******************************************************************************
*函数名：
*函数功能：剪切一个节点（从链表中断开，但不释放）
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void cut_node(pnode pcut)
{
	/*判断链表是否为空*/
	if (isempty_doublelist(pcut))
	{
		printf("链表只有一个节点，无法剪切\n");
		return;
	}
	
	/*剪切节点*/
	pcut->prev->next = pcut->next;
	pcut->next->prev = pcut->prev;
}

/*******************************************************************************
*函数名：
*函数功能：特殊奇偶排序
*函数参数：
*函数返回值：
*函数说明：奇数节点正序，偶数节点逆序，且奇数节点在偶数节点前面。
例如，1 2 3 4 5 6 7 8 9→1 3 5 7 9 8 6 4 2
*******************************************************************************/
void sort_oddeven(pnode head)
{
	pnode p,q;
	p = head->prev;
	
	while(p != head)
	{
		q = p;
		p = p->prev;
		
		if ((q->data)%2 == 0)//如果是偶数
		{
			cut_node(q);
			insert_node2(head,q);
		}
	}
}

/*******************************************************************************
*函数名：
*函数功能：双向链表排序（从小到大）
*函数参数：
*函数返回值：
*函数说明：只交换数据域，不改变指针域
*******************************************************************************/
void sort_doublelist(pnode head)
{
	int temp;
	pnode p,q;
	
	for (p = head->next; p != head; p = p->next)
		for (q = p->next; q != head; q = q->next)
		{
			if (p->data > q->data)
			{
				temp = p->data;
				p->data = q->data;
				q->data = temp;//交换data域
			}
		}	
}

/*******************************************************************************
*函数名：
*函数功能：双向链表排序2（从小到大）
*函数参数：
*函数返回值：
*函数说明：数据域和指针域都交换
1 3 5 6 4 2→1 2 3 4 5 6
*******************************************************************************/
void sort_doublelist2(pnode head)
{
	
}

/*******************************************************************************
*函数名：
*函数功能：
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/

